package mashibing.class17;

/**
 * 汉诺塔问题（暴力递归）
 */
public class Class17_2_Hanoi {

    // 版本1、把所有挪到右边，把n-1放到中间，再把最底下放到右边，以此类推
    public static void hano1(int n) {
        leftToRight(n);
    }

    private static void leftToRight(int n) {
        if (n == 1) {
            System.out.println("move left to right: " + 1);
            return;
        }
        leftToMid(n - 1);
        System.out.println("move left to right: " + n);
        midToRight(n - 1);
    }

    private static void leftToMid(int n) {
        if (n == 1) {
            System.out.println("move left to mid: " + 1);
            return;
        }
        leftToRight(n - 1);
        System.out.println("move left to mid: " + n);
        rightToMid(n - 1);
    }

    private static void midToLeft(int n) {
        if (n == 1) {
            System.out.println("move mid to left: " + 1);
            return;
        }
        midToRight(n - 1);
        System.out.println("move mid to left: " + n);
        rightToLeft(n - 1);
    }

    private static void midToRight(int n) {
        if (n == 1) {
            System.out.println("move mid to right: " + 1);
            return;
        }
        midToLeft(n - 1);
        System.out.println("move mid to right: " + n);
        leftToRight(n - 1);
    }

    private static void rightToLeft(int n) {
        if (n == 1) {
            System.out.println("move right to left: " + 1);
            return;
        }
        rightToMid(n - 1);
        System.out.println("move right to left: " + n);
        midToLeft(n - 1);
    }

    private static void rightToMid(int n) {
        if (n == 1) {
            System.out.println("move right to mid: " + 1);
            return;
        }
        rightToLeft(n - 1);
        System.out.println("move right to mid: " + n);
        leftToMid(n - 1);
    }

    /**
     * 版本2
     */
    public static void hano2(int n) {
        fromTo(n, "left", "right", "mid");
    }

    public static void fromTo(int n, String from, String to, String other) {
        if (n == 1) {
            System.out.println("move " + from + " to " + to + ": " + n);
            return;
        }
        fromTo(n - 1, from, other, to);
        System.out.println("move " + from + " to " + to + ": " + n);
        fromTo(n - 1, other, to, from);
    }


    public static void main(String[] args) {
        hano1(3);
        System.out.println("-----------------------");
        hano1(3);
        System.out.println("-----------------------");
    }
}
